/**
 * Created by ACER on 2019/3/26.
 */

/**
 * 查找算法
 */
public class LookUpTest {
    static int[] hash=new int[200];
    public static void main(String[] args) {
        int[] list = getList(100);
        //int i = orderLookup(list, 40);
        //折半查找
        int[] sortList = chooseSort(list);
        int i = halveLookup(sortList, 40);

        //顺序查找
        if (i == -1) {
            System.out.println("未找到");
        } else {
            System.out.println("找到数的索引位置为" + i);
        }


        //哈希查找
        testHash(list,154,51);
    }

    //顺序查找
    public static int orderLookup(int[] list, int key) {
        for (int i = 0; i < list.length; i++) {
            if (list[i] == key) {
                return i;
            }
        }
        return -1;

    }

    //折半查找-----适用于有顺序的查找
    public static int halveLookup(int[] list, int key) {
        int low = 0, high = list.length - 1;
        while (low <= high) {
            int middle = (low + high) / 2;
            //
            if (list[middle] == key) {
                return middle;
            }
            //值在前半段
            else if (key < list[middle]) {

                high = middle - 1;
            } else {
                low = middle + 1;
            }
        }
        return -1;
    }


    //哈希查找，通过hash算法，在hash表里面进行查找
    //测试hash查找
    public static void testHash(int[] list,int length,int key){
        //插入hash表
        for (int i=0;i<list.length-1;i++){
            insertHash(length,list[i]);
        }
        //hash查找
        int index = searchHash(hash, length, key);
        if (index!=-1){
            System.out.println("hash查找索引位置为"+index);
        }
        else {
            System.out.println("不在哈希表中");
        }

    }
    //查找hash
    public static int searchHash(int[] list, int length, int key) {
        int hashAddress = key % length;
        while (list[hashAddress] != 0 && list[hashAddress] != key) {
            hashAddress = (++hashAddress) % length;
        }
        if (list[hashAddress] == 0) {
            return -1;
        }
        return hashAddress;
    }

    //插入哈希表，通过取余法插入，通过开放寻址法解决冲突
    public static void insertHash( int length, int key) {
        int hashAddress = key % length;
        //解决冲突
        while (hash[hashAddress] != 0) {
            hashAddress = (++hashAddress) % length;
        }
        //放入字典
        hash[hashAddress] = key;
    }

    //生成排序的数字（1-100）
    public static int[] getList(int size) {
        System.out.print("排序前数字：\t");
        int baseNum[] = new int[size];
        for (int i = 0; i < size; i++) {
            int v = (int) (Math.random() * 100);
            baseNum[i] = v;
            System.out.print(v + "\t");
        }
        return baseNum;
    }

    //选择排序
    public static int[] chooseSort(int[] list) {

        for (int i = 0; i < list.length - 1; i++) {
            //假设下标值最小
            int tempIndex = i;
            for (int j = i + 1; j < list.length - 1; j++) {
                if (list[tempIndex] > list[j]) {
                    tempIndex = j;
                }
            }
            //数据交换
            int temData = list[tempIndex];
            list[tempIndex] = list[i];
            list[i] = temData;

        }

        //printSortResult("选择排序", list);
        return list;
    }


}


